An ε-universal-hash-function family from a set A to a set B represents a set of functions from set A to set B where the number of elements h of H which is a set of functions and which satisfies h(x)=h(y) with respect to given two different arbitrary elements x, y belonging to the set A is equal to or less than ε×|H|. |H| is the number of elements of the set H. Hereinafter, the number of elements of an arbitrary set S is represented by |S|. The ε-universal-hash-function family is used for improvement of secrecy in a message authentication code or quantum key distribution, as described in C. H. Bennett, G. Brassard, C. Crepeau, and U. Maurer “Generalized Privacy Amplification”, IEEE Trans. Information Theory vol. 41, no. 6, 1995, pp. 1915-1923 (Non-Patent Document 1) and D. R. Stinson, “Universal Hashing and Authentication Codes”, Designs, Codes and Cryptography, vol. 4, 1994, pp. 369-380 (Non-Patent Document 2).
A method for realizing a conventional ε-universal-hash-function family is described in Non-Patent Document 2 and D. R. Stinson, “Combinatorial techniques for Universal Hashing”, Journal of Computer and System Sciences, vol. 48, No. 2, 1994, pp. 337-346 (Non-Patent Document 3). Further, Non-Patent Documents 2 and 3 describe the lower bound of the number of elements of ε-universal-hash-function family. When the ε-universal-hash-function family is used in a message authentication code or quantum key distribution, it is desirable that the number of elements of the ε-universal-hash-function family used be small in the view point of efficiency. However, the conventional technique can only achieve the lower bound of the number of elements with respect to only extremely-limited parameters. Known techniques for constructing the ε-universal-hash-function family for an input set A and an output set B where the lower bound cannot be achieved include, as described in Non-Patent Document 1, a method including the steps of: selecting an element k from the set A; calculating a product between the element k and the input data x; and applying a reduction conversion of the set A to set B. In this case, although the value of ε is 1/|B|, which means that the number of elements of the ε-universal-hash-function family is equal to the number of elements of the set A, |A|/|B| which is the lower bound of the number of elements described in Patent Document 3 is not achieved. Further, although Martin Boesgaard, Thomas Christensen and Erik Zenner, “Badger—A Fast and Provably Secure MAC”, Proceedings of Applied Cryptography and Network Security, ACNS2005, Lecture Notes in Computer Science, vol. 3531, Springer Verlag, 2005, pp. 176-191 (Non-Patent Document 4) describes a method for constructing the ε-universal-hash-function family, the method described therein is a general method for constructing a hash function aiming to increase in the calculation speed of a hash function, and thus not aiming to a reduction of the number of elements of a hash function set.
Further, a method (method for achieving the lower bound of the number of elements of the ε-universal-hash-function family) has scarcely been known which is applied in the case where the number of elements of the set B, which is the output set, is large, even though there has been available a useful technique such as a quantum key distribution.
An error correction method referred to as “cascade” is described in G. Brassard, L. Salvail, “Secret-Key Reconciliation by Public Discussion”, Proc. Eurocrypto '93, Lecture Notes in Computer Science, Vol. 765, Springer Verlag, 1994, pp. 410-423 (Non-Patent Document 5).
Further, a system that cuts out some bits of input data and performs hash calculation on the cut out data is described in Patent Publication JP-2001-134178A (paragraph [0018], FIG. 4).
As described above, in the ε-universal-hash-function family realized by the conventional techniques, the input set and output set where the number of elements is minimized are limited. However, it is desirable to perform calculation of a hash function belonging to the ε-universal-hash-function family having a reduced number of elements.